Il periodo di dominazione araba finì nel 1091, quando l'isola venne conquistata dai Normanni provenienti dalla Contea di Sicilia, alla guida di Ruggero d'Altavilla. L'arcipelago entrò così nell'orbita siciliana e fu posto sotto il controllo dei membri della casa normanna di Sicilia, sebbene di fatto si trattasse di un controllo poco più che nominale. Nel 1191 Margarito di Brindisi sbarcò nuovamente sull'isola e venne nominato primo conte di Malta. I legami dell'isola con la Sicilia si fecero conseguentemente sempre più stretti e il feudo fu successivamente concesso alle famiglie della più alta nobiltà siciliana stabilitasi nella piccola isola quali i Conti di Modica, Manfredi III Chiaramonte alla fine del Trecento, Bernardo Cabrera nei primi decenni del Quattrocento, i Moncada e i Monroy, pur tornando spesso a essere governata direttamente dai sovrani o da loro familiari. La nobiltà maltese venne istituita in quest'ultimo periodo e circa trentadue titoli nobiliari permangono tuttora, il più vecchio dei quali è il Baronato di Djar il Bniet e Bucana.

Malta entrò quindi definitivamente nell'orbita culturale dell'Europa latina, sebbene l'influsso della fede e della cultura di origini arabe continuasse ad essere largamente presente fino al XIII secolo. A seguito dell'incorporazione come feudo, le sorti della piccola contea insulare seguirono nei secoli successivi quelle del Regno di Sicilia; a succedersi nel dominio dell'isola furono fra il XIII e il XVI secolo gli Hohenstaufen (Svevi), gli Angioini e gli Aragonesi. Nel 1283 questi ultimi sconfissero in uno scontro navale combattuto nel Porto Grande presso l'odierna Valletta una flotta angioina, conquistando l'arcipelago maltese alla Corona d'Aragona.